package Sort.十大排序;

import java.util.*;

//十大经典排序
public class TopTenClassicsRanking {
    /**
     * ***********************  插入排序 *******************************
     * 把一个数插入到有序区间，保持这个区间有序，
     * 个人理解 ： 按照索引 依次比较
     * @param a  数组
     */
    public static void insertSort(int[] a){
        //因为是比较 索引位置的数 和 它后一位的数， 最后依次 比较相比的数的 索引是 a[a.length -2] 和 a[length -1]
        for(int i = 0; i < a.length -1; i++){
            int temp;
            while(i >= 0){
                if(a[i] > a[i+1]){
                    temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                    --i;
                }else{
                    break;
                }
            }
        }
    }

    /**
     * 希尔排序   ---> 减少增量法
     * 个人理解 ： 每次减少增量， 依次比较距离为增量的索引的大小并交换，当增量为1时，也就时一个插入排序
     * @param a
     */
    public static void ShellSort(int[] a){
        int grp = a.length;
        while(true){
            grp /= 2;  //每次增量减半
            for(int i = 0; i < grp; i++){
                for(int j = i + grp; j < a.length; j += grp){
                    int k = j - grp;
                    while(k > 0 && a[k] > a[k+grp]){
                        int temp = a[k];
                        a[k] = a[k+grp];
                        a[k+grp] = temp;
                        k -= grp;
                    }
                }
            }
            if(grp == 1){
                break;
            }
        }
    }


    /**
     * 选择排序  ——> 分为 一个排序好的数组 和 一个未排序好的数字
     *          在未排序的数组选择 最小的数 放入有序数组里面
     * @param arr
     */
    public static void checkSort(int[] arr){
        int temp;
        for(int i = 0; i < arr.length -1; i++){
            int minIndex = i;  //最小数的索引
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if(i != minIndex){
                temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    /**
     * **************  把数组看成一个二叉树  *************
     * *******************  0   **********************
     * ****************** 1    2  ********************
     * **************** 3  4  5  6  ******************
     * ******************  堆排序    *****************
     *
     * @param array
     * @return
     */
    public static int[] heapSort(int[] array) {
        //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length);  //调整堆
        }

        // 上述逻辑，建堆结束
        // 下面，开始排序逻辑
        for (int j = array.length - 1; j > 0; j--) {
            // 元素交换,作用是去掉大顶堆
            // 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
            swap(array, 0, j);
            // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
            // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
            // 而这里，实质上是自上而下，自左向右进行调整的
            adjustHeap(array, 0, j);
        }
        return array;
    }

    /**
     * 整个堆排序最关键的地方
     * @param array 待组堆
     * @param i 起始结点
     * @param length 堆的长度
     */
    public static void adjustHeap(int[] array, int i, int length) {
        // 先把当前元素取出来，因为当前元素可能要一直移动
        int temp = array[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
            // 让k先指向子节点中最大的节点
            if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子树,并且右子树大于左子树
                k++;
            }
            //如果发现结点(左右子结点)大于根结点，则进行值的交换
            if (array[k] > temp) {
                swap(array, i, k);
                // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
                i  =  k;
            } else {  //不用交换，直接终止循环
                break;
            }
        }
    }

    /**
     * 交换元素
     * @param arr
     * @param a 元素的下标
     * @param b 元素的下标
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            for(int j = 1; j < arr.length-1- i; j++){
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public static int[] quickSort(int[] arr, int start, int end){
        int pivot = arr[start];
        int i = start;
        int j = end;
        while(i < j){
            while( arr[j] > pivot){
                j--;
            }
            while(arr[i] < pivot){
                i ++;
            }
            if( arr[i] <= arr[j]){
                i ++;
            }else{
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if(i-1 > start) arr = quickSort(arr,start,i-1);
        if(j+1 < end) arr=quickSort(arr,j+1,end);
        return arr;
    }

    /**
     * 归并排序  ==>  https://www.cnblogs.com/chengxiao/p/6194356.html
     * @param arr
     */
    public static void mergeSort(int arr[]){
        int[] temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }

    public static void sort(int[] arr, int left, int right, int[] temp){
        if(left < right){
            int mid = (left + right) /2;
            sort(arr,left,mid,temp);  //左序列 递归排序
            sort(arr,mid+1,right,temp); // 有序列 递归排序
            merger(arr,left,mid,right,temp);
        }
    }
    /**
     *
     * @param arr  需要归并排序数组
     * @param left 数组初始索引
     * @param mid   中间索引
     * @param right  最大索引
     * @param temp 与 arr 长度相同，同来存放排序好 的数组
     */
    public static void merger(int[] arr, int left, int mid, int right, int[] temp){
        int i = left ;    // 左序列指针
        int j = mid + 1 ;  // 右序列指针
        int t = 0 ;     //临时数组指针
        while(i <= mid  && j <= right){  // 左序列 甚于元素填入 temp中
            if(arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else{
                temp[t++] = arr[j++];
            }
        }
        while(i <= mid){   // 左序列 剩余元素填入temp中
            temp[t++] = arr[i++];
        }
        while(j <= right){ // 右序列 剩余元素填入temp中
            temp[t++] = arr[j++];
        }

        t = 0;
        // 将 temp 元素拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }

    /**
     * 计数排序
     * 假设数组{1，3，5，7，9}
     * arr.length = 5;
     * newArr.length = 9;
     * @param arr
     */
    public static void countSort(int[] arr){
        int min = arr[0];
        int max = arr[0];
        for(int i = 0; i < arr.length; i++){
            if(arr[i] < min){
                min = arr[i];
            }
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int size = max-min +1;
        int[] newArr = new int[size];
        for(int i = 0; i < arr.length; i++){
            int needSortNumIndex = arr[i] - min;
            newArr[needSortNumIndex] ++;
        }
        int index = 0;
        for(int i = 0; i < size; i++){
            while(newArr[i] > 0){
                //索引 + 最小的数
                arr[index++] = i + min;
                --newArr[i];
            }
        }
    }


    public static void main(String[] args) {
        int[] a = {1,56,7,65,32,4,2,56,13,1};
//        TopTenClassicsRanking.insertSort(a);
//        TopTenClassicsRanking.ShellSort(a);
//        TopTenClassicsRanking.checkSort(a);
/*        TopTenClassicsRanking.heapSort1(a);*/
/*        TopTenClassicsRanking.bubbleSort(a);*/
//        TopTenClassicsRanking.quickSort(a,0, a.length-1);
//        TopTenClassicsRanking.mergeSort(a);
        TopTenClassicsRanking.countSort(a);
        for(int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "\t");
        }
        System.out.println("-----------------");

        String ab = " abc ac ";
        ab = ab.trim();
        String[] strs = "    ".split(" ");
        for(String s: strs){
            System.out.println(s);
        }

    }



}
